package code.jzh.compiler.scanner;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import code.jzh.compiler.util.Constants;

public class MinimalDFA {
	public static int idGenerator = 1;
	public MinimalDFAState start;
	
	public Set<MinimalDFAState> minimalDFAStates = new HashSet<MinimalDFAState>();
	
	public static MinimalDFA buildMinimalDFA(DFA dfa) {
		Set<MinimalDFAState> workSet = initialMinimalDFAState(dfa);
		splitMinimalDFAStates(workSet, dfa);
		
		MinimalDFA minimalDFA = new MinimalDFA();
		minimalDFA.minimalDFAStates = workSet;
		
		for(MinimalDFAState miniDFAState : workSet) {
			for(DFAState dfaState : miniDFAState.dfaStates) {
				if(dfaState.accepted)
					miniDFAState.accepted = true;
				if(dfaState.started) {
					miniDFAState.started = true;
					minimalDFA.start = miniDFAState;
				}
			}
		}
		
		buildMinimalDFAEdges(minimalDFA, dfa);
		return minimalDFA;
	}
	
	public static void buildMinimalDFAEdges(MinimalDFA minimalDFA, DFA dfa) {
		for(MinimalDFAState minimalDFAState : minimalDFA.minimalDFAStates) {
			for(char c : Constants.charList) {
				DFAState firstDFAState = null;
				for(DFAState dfaState : minimalDFAState.dfaStates) {
					firstDFAState = dfaState;//取出第一个
					break;
				}
				Integer targetDFAStateId = firstDFAState.edges.get(c);
				if(targetDFAStateId==null)
					continue;
				DFAState targetDFAState = dfa.getDFAStateById(targetDFAStateId);
				int targetMinimalDFAStateId = getMinimalDFAStateIdByDFAState(targetDFAState, 
						minimalDFA.minimalDFAStates);
				minimalDFAState.addEdge(c, targetMinimalDFAStateId);
			}
		}
	}
	
	public static Set<MinimalDFAState> splitMinimalDFAStates(Set<MinimalDFAState> workSet, DFA dfa) {
		int originWorkSetSize = -1;
		do {
			originWorkSetSize = workSet.size();
			Set<MinimalDFAState> tmpSet = new HashSet<MinimalDFAState>();
			tmpSet.addAll(workSet);
			for(MinimalDFAState minimalDFAState : tmpSet) {
				workSet = splitMinimalDFAState(minimalDFAState, workSet, dfa);
			}
		}while(originWorkSetSize!=workSet.size());
		return workSet;
	}
	
	public static Set<MinimalDFAState> splitMinimalDFAState(MinimalDFAState minimalDFAState, Set<MinimalDFAState> workSet, DFA dfa) {
		for(char c : Constants.charList) {
			boolean isSplit = splitMinimalDFAStateByChar(minimalDFAState, workSet, c, dfa);
			if(isSplit)
				break;
		}
		return workSet;
	}
	
	public static boolean splitMinimalDFAStateByChar(MinimalDFAState minimalDFAState, Set<MinimalDFAState> workSet, 
			char c, DFA dfa){
		//key: minimalDFAState的id value: 该minimalDFAState对应的DFAState
		Map<Integer, Set<DFAState>> map = new HashMap<Integer, Set<DFAState>>();
		for(DFAState dfaState : minimalDFAState.dfaStates) {
			Integer targetDFAStateId = dfaState.edges.get(c);
			if(targetDFAStateId==null){
				Set<DFAState> nullDFAStateSet = map.get(-1);
				if(nullDFAStateSet==null) {
					nullDFAStateSet = new HashSet<DFAState>();
					map.put(-1, nullDFAStateSet);
				}
				nullDFAStateSet.add(dfaState);
			}else{
				DFAState targetDFAState = dfa.getDFAStateById(targetDFAStateId);
				int targetMinimalDFAStateId = getMinimalDFAStateIdByDFAState(targetDFAState, workSet);
				Set<DFAState> dfaStateSet = map.get(targetMinimalDFAStateId);
				if(dfaStateSet==null) {
					dfaStateSet = new HashSet<DFAState>();
					map.put(targetMinimalDFAStateId, dfaStateSet);
				}
				dfaStateSet.add(dfaState);
			}
		}
		if(map.size()>1) {//需要拆分
			workSet.remove(minimalDFAState);//首先移除原来的minimalDFAState
			boolean first = true;//拆分后的第一个miniDFAState id不变 沿用之前的id
			for(Integer minimalDFAStateId : map.keySet()) {
				Set<DFAState> dfaStates = map.get(minimalDFAStateId);
				MinimalDFAState splitMinimalDFAState = null;
				if(first) {
					splitMinimalDFAState = new MinimalDFAState(minimalDFAState.id);
					first = false;
				}else {
					splitMinimalDFAState = new MinimalDFAState(idGenerator++);
				}
				splitMinimalDFAState.dfaStates = dfaStates;
				workSet.add(splitMinimalDFAState);
			}
//			printWorkSet(workSet);
			return true;
		}
		return false;
	}
	
	public static Set<MinimalDFAState> initialMinimalDFAState(DFA dfa){
		Set<MinimalDFAState> set = new HashSet<MinimalDFAState>();
		MinimalDFAState acceptedState = new MinimalDFAState(idGenerator++);
		MinimalDFAState noAcceptedState = new MinimalDFAState(idGenerator++);
		for(DFAState dfaState : dfa.dfaStates) {
			if( dfaState.accepted ) {
				acceptedState.dfaStates.add(dfaState);
			}else {
				noAcceptedState.dfaStates.add(dfaState);
			}
		}
		if(acceptedState.dfaStates.size()>0)
			set.add(acceptedState);
		if(noAcceptedState.dfaStates.size()>0)
			set.add(noAcceptedState);
		return set;
	}
	
	public static int getMinimalDFAStateIdByDFAState(DFAState dfaState, Set<MinimalDFAState> workSet) {
		for(MinimalDFAState minimalDFAState : workSet) {
			if(minimalDFAState.dfaStates.contains(dfaState))
				return minimalDFAState.id;
		}
		return -1;
	}
	
	public MinimalDFAState move(MinimalDFAState current, char c) {
		Integer nextStateId = current.edges.get(c);
		if(nextStateId==null)
			return null;
		
		return getMinimalDFAStateById(nextStateId);
	}
	
	public MinimalDFAState getMinimalDFAStateById(int minimalDFAStateId) {
		for(MinimalDFAState minimalDFAState : minimalDFAStates) {
			if(minimalDFAState.id == minimalDFAStateId)
				return minimalDFAState;
		}
		return null;
	}
	
	public static void printWorkSet(Set<MinimalDFAState> workSet){
		for(MinimalDFAState m : workSet){
			System.out.print("MinimalDfaState ID:  "+m.id+"\t DFAStates: ");
			for(DFAState d : m.dfaStates)
				System.out.print(d.id+" ");
			System.out.println();
		}
		System.out.println();
	}
	
	public void printMinimalDFA() {
		for(MinimalDFAState minimalDFAState : minimalDFAStates) {
			System.out.println("MinimalDFA STATE: "+minimalDFAState.id
					+(minimalDFAState.accepted?"\taccepted!!!":"")
					+(minimalDFAState.started?"\tstarted!!!":""));
			for(char c : minimalDFAState.edges.keySet()) {
				System.out.println("\t"+minimalDFAState.id+"->"+c+"->"+minimalDFAState.edges.get(c));
			}
		};
	}
}
